'''
CF 1864E
For each a, consider prefix of a's bits matching
prefix of b's bits and then having a difference in bit.
'''
class Node:
def __init__(self):
self.L = None
self.R = None
self.subtree_cnts = 0
def main():
mod = 998244353
t = int(input())
allans = []
for _ in range(t):
n = int(input())
s = readIntArr()
trie_address = [-1, -1] subtree_cnts = [0, 0]
for v in s:
u = 0
for i in range(29, -1, -1):
if (v & (1 << i)) == 0:
if trie_address[u] == -1:
trie_address.extend([-1, -1])
trie_address[u] = len(trie_address) - 2
subtree_cnts.extend([0, 0])
u = trie_address[u]
else:
if trie_address[u + 1] == -1:
trie_address.extend([-1, -1])
trie_address[u + 1] = len(trie_address) - 2
subtree_cnts.extend([0, 0])
u = trie_address[u + 1]
subtree_cnts[u] += 1
ans = 0
for v in s:
a_turn = True
n_turns = 1
u = 0
for i in range(29, -1, -1):
if (v & (1 << i)) == 0:
if trie_address[u + 1] != -1: if a_turn:
ans += (n_turns * subtree_cnts[trie_address[u + 1]]) % mod
ans %= mod
else:
ans += ((n_turns + 1) * subtree_cnts[trie_address[u + 1]]) % mod
ans %= mod
u = trie_address[u]
else:
if trie_address[u] != -1: if a_turn:
ans += ((n_turns + 1) * subtree_cnts[trie_address[u]]) % mod
ans %= mod
else:
ans += (n_turns * subtree_cnts[trie_address[u]]) % mod
ans %= mod
a_turn = not a_turn
n_turns += 1
u = trie_address[u + 1]
ans += (n_turns * subtree_cnts[u]) % mod
ans %= mod
denominator = (n * n) % mod
ans = (ans * pow(denominator, mod - 2, mod)) % mod
allans.append(ans)
multiLineArrayPrint(allans)
return
import sys
input=sys.stdin.buffer.readline
def oneLineArrayPrint(arr):
print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
def readIntArr():
return [int(x) for x in input().split()]
def makeArr(defaultValFactory,dimensionArr): dv=defaultValFactory;da=dimensionArr
if len(da)==1:return [dv() for _ in range(da[0])]
else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
def queryInteractive(a, b):
print('? {} {}'.format(a, b))
sys.stdout.flush()
return int(input())
def answerInteractive(ans):
print('! {}'.format(ans))
sys.stdout.flush()
inf=float('inf')
from math import gcd,floor,ceil
import math
for _abc in range(1):
main()#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t){
t--;
long long n, i, j, r, m, ans=0;
cin >> n;
long long s[n];
for(i=0; i<n; i++){
cin >> s[i];
}
sort(s, s+n);
bool a[n][31];
for(i=0; i<n; i++){
a[i][0]=0;
}
for(i=0; i<n; i++){
for(j=1; j<=30; j++){
if(s[i]%2==1){
a[i][j]=1;
}
else{
a[i][j]=0;
}
s[i]/=2;
}
}
long long b[31];
for(i=0; i<=30; i++){
b[i]=0;
}
for(i=0; i<n; i++){
a[i][0]=1;
for(j=30; j>-1; j--){
if(a[i][j]!=a[i-1][j]){
break;
}
}
r=30-j;
for(j=0; j<=30; j++){
if(j>r){
b[r]+=b[j];
b[j]=0;
}
}
b[30]++;
r=0;
for(j=0; j<=30; j++){
if(j==30){
ans=(ans+(2*b[30]-1)*(r+1))%mod;
continue;
}
ans=(ans+(2*r+3)*b[j])%mod;
if(a[i][30-j]){
r++;
}
}
a[i][0]=0;
}
for(i=0; i<n; i++){
if((i*mod+1)%n==0){
m=(i*mod+1)/n;
m=m*m;
}
}
ans=ans%mod;
m=m%mod;
ans=(ans*m)%mod;
cout << ans << "\n";
}
}
Cutting a material | Bubble Sort |
Number of triangles | AND path in a binary tree |
Factorial equations | Removal of vertices |
Happy segments | Cyclic shifts |
Zoos | Build a graph |
Almost correct bracket sequence | Count of integers |
Differences of the permutations | Doctor's Secret |
Back to School | I am Easy |
Teddy and Tweety | Partitioning binary strings |
Special sets | Smallest chosen word |
Going to office | Color the boxes |
Missing numbers | Maximum sum |
13 Reasons Why | Friend's Relationship |
Health of a person | Divisibility |
A. Movement | Numbers in a matrix |